Computer networks are very flexible. A network can be viewed as a conduit for messages, in that data enters the network at one or more points, is transmitted through the network, and leaves the network at one or more other points. A network can also be viewed as a repository of data and/or as a source of data. A network is a repository if data enters the network at one or more points and travels to a storage location in the network. A network is a source of data if previously stored data or internally generated data travels out of the network or is sent to a different location in the network.
The flexibility of a given network arises in part from the internal organization of the network as a collection of linked nodes. When data is sent from one user to another, or between a user and a repository, the data travels in turn from node to node to node until it reaches its destination. Because data can often leave a given node over any of several links, a large number of routes may exist between any two nodes which are not immediate neighbors of one another. Often, however, some routes are better than others. The process of choosing a route in a particular situation is called "routing" or "route selection." Routes are sometimes called "paths."
Because route selection is both important and challenging, it has been the object of much study and experimentation. One set of challenges involves selecting appropriate ways to measure the costs associated with different network links and nodes. For instance, a weight may be associated with each link and each node in a network based on the item's measured or expected performance; the weight may reflect characteristics such as bandwidth, latency, reliability, memory size, and/or processor speed.
A second set of challenges involves mapping connectivity by identifying which links and nodes are connected. Various exploration protocols have been devised and applied to map the connections in networks. One main goal of such protocols is performing the mapping with the smallest necessary amount of network bandwidth and other resources. Another goal is providing sufficiently rapid updates when a node or link does down, is removed, is added, or returns to service.
Another set of challenges involves using topology information (information about weights and/or connectivity) to identify the desirable paths in a given network at a given time. Various methods can be used to identify the "best" route between two nodes, namely, the route having the lowest total weight. If the computing resources needed to identify the best route are too expensive, then "near-optimal" or "pretty good" routes may be identified instead.
Further challenges are posed by the question of when and how to update topology information. Updates may include changes to current routing information and/or the addition of wholly new routing information. Routing protocols such as the RIP (Routing Information Protocol) and OSPF (Open Shortest Path First) protocols allow routers to request and obtain information from neighboring routers about paths to other routers.
Instead of trying to compute the entire route from scratch each time, some systems store partial computational results and reuse them when possible. For instance, U.S. Pat. No. 5,321,815 issued to Bartolanzo, Jr. et al. describes a process for selecting a least weight path between two nodes in a network using partial trees which were created and cached in prior route selection operations.
Some systems also distribute the task of selecting a route. For instance, U.S. Pat. No. 5,398,012 issued to Derby et al. describes a distributed process for determining the best communication route from a source end station to a destination end station. Network nodes, at the interface between a wide area network ("WAN") and each subnetwork , contain access agents to control the communication flow between the wide area network and an end station in the subnetwork. The task of selecting the best route between two end stations is distributed between the access agents at the WAN interface in the first subnetwork and the access agents at the WAN interface in the second subnetwork.
However, previous work has not adequately addressed the problem of providing secured access to the network topology. In general, the route selection agents and processes in a given network have been given ready access to detailed information about the network's nodes and about the links between the nodes. In some networks, this poses a security risk, because such knowledge could be used to intercept or eavesdrop on communications, to masquerade as an authorized user, and/or to insert spurious data packets into the network.
Accordingly, it would be an advance to provide an approach to routing which takes advantage of existing tools but also enhances the security of network topology information, and which does so in an efficient manner.
Such an approach to secure network topology storage and use is described and claimed below.